package Z.dailyExercise._0115;

public class _1351_统计有序矩阵中的负数 {


    /**
     * 自解：横向遍历 碰到第一个为负数的 就停止
     * 假设第一个为负数的index=j 那么本数组中负数 n-index
     * 优化 可以先比较长和宽 从短的那一方进行遍历
     * ===再次优化：从最底下开始往上遍历 遇到整个一行都没有的直接就返回接轨
     * 并且将j声明为全局变量 这样就从上一次遍历的那一行的那一列开始往后遍历
     * @param grid
     * @return
     */

    public int countNegatives(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        int res =0;
        int j = 0;
        for (int i=m-1;i>=0;i--) {
            while (j < n && grid[i][j] >= 0) {
                j++;
            }
            if (j == n) {
                return res;
            }

            res += n - j;

        }



        return res;



    }


}
